const TripleNode = require('./树节点/triplenode')

//宏
const LEFT = 'LEFT_HIGH'
const RIGHT = 'RIGHT_HIGH'
// 平衡二叉树
class BalencedBinaryTree {
    //构造器
    constructor(root = null) {
        this.root = root
    }
    //中序遍历
    inOrder() {
        this._inOrder(this.root)
        process.stdout.write('\n')
    }
    _inOrder(subroot) {
        if (subroot === null) {
            return
        } else {
            this._inOrder(subroot.left)
            process.stdout.write(subroot.toString() + " ")
            this._inOrder(subroot.right)
        }
    }
    // 数组构造平衡二叉树
    static createByArr(arr) {
        let bbt = new BalencedBinaryTree
        for (let i = 0; i <= arr.length - 1; i++) {
            bbt.AVL_insert(arr[i])
        }
        return bbt
    }
    // 搜索操作
    AVL_research(element) {
        let p = this.root
        while (p !== null && p.data !== element) {
            if (element < p.data) {
                p = p.left
            } else {
                p = p.right
            }
        }
        return p
    }
    // 插入操作
    AVL_insert(element) {
        // 普通排序树的插入操作
        let newNode = new TripleNode(element)
        if (this.root === null) {
            this.root = newNode
        } else {
            this._AVLInsertByRecursion(this.root, newNode)
        }
        // 平衡性检查，从newNode开始搜索祖先，检查每一个祖先元素的平衡因子
        this.balance(newNode)
    }
    _AVLInsertByRecursion(subRoot, newNode) {
        if (newNode.data < subRoot.data) {
            if (subRoot.left === null) {
                subRoot.left = newNode
                newNode.parent = subRoot
            } else {
                this._AVLInsertByRecursion(subRoot.left, newNode)
            }
        } else if (newNode.data > subRoot.data) {
            if (subRoot.right === null) {
                subRoot.right = newNode
                newNode.parent = subRoot
            } else {
                this._AVLInsertByRecursion(subRoot.right, newNode)
            }
        } else {}
    }
    // 传入节点及其所有祖先节点的平衡调整
    balance(newNode) {
        while (newNode !== null) {
            // 找失衡节点时，按从靠近插入节点开始向上找祖先的顺序查找
            // 找到就旋转，然后继续向上找
            //L\R的判断是以失衡节点为基准的
            // L*型，左子树高，最后一个旋转一定是右旋
            // R*型，右子树高，最后一个旋转一定是左旋
            if (this.calcBalanceValue(newNode) === 2) {
                // 左子树高，需要右旋（LL）或先左旋后右（LR）
                this.operateAfterInsertion(newNode, LEFT)
            } else if (this.calcBalanceValue(newNode) === -2) {
                //右子树高，需要左旋（RR）或先右旋，后左旋
                this.operateAfterInsertion(newNode, RIGHT)
            } else {}
            newNode = newNode.parent
        }

    }
    // 传入节点的平衡因子计算
    calcBalanceValue(node) {
        return (node !== null) ? this.getMaxDepth(node.left) - this.getMaxDepth(node.right) : 0
    }
    // 以传入节点为根的最大深度计算
    getMaxDepth(node) {
        if (node === null) {
            return 0
        } else {
            return 1 + Math.max(this.getMaxDepth(node.left), this.getMaxDepth(node.right))
        }
    }
    // 调整操作
    operateAfterInsertion(newNode, type) {
        if (type === LEFT) {
            // 取失衡节点的左节点，若左节点因子为1，则LL；-1则LR
            // LR型前置操作，先左旋
            let newNode_left = newNode.left
            if (this.calcBalanceValue(newNode_left) === -1) {
                this.leftRotation(newNode_left)
            }
            //LL,LR统一的右旋操作
            this.rightRotation(newNode)
        } else if (type === RIGHT) {
            let newNode_right = newNode.right
            if (this.calcBalanceValue(newNode_right) === 1) {
                this.rightRotation(newNode_right)
            }
            this.leftRotation(newNode)
        }
    }
    // 右旋转调整（可直接解决LL型）
    rightRotation(newNode) {
        /** 
         * 传入失衡节点
            对失衡节点进行右下旋转造操作，具体算法描述如下：
                1. 失衡节点的左子树节点代替它的位置
                2. 失衡节点及失衡节点的右子树成为失衡节点的左子树节点的右子树
                3. 失衡节点的左子树若有右子树，则其右子树成为失衡节点的左子树
            返回失衡节点的左子树（即代替失衡节点位置的节点被返回）
        */
        if (newNode !== null) {
            // 保存失衡节点的左子树
            let newNode_left = newNode.left
            // 处理失衡节点的左子树的右子树
            newNode.left = newNode_left.right
            if (newNode_left.right !== null) {
                //处理处理失衡节点的左子树的右子树的父节点
                newNode_left.right.parent = newNode
            }
            //将失衡节点的左子树父节点改为失衡节点的父节点（如果有）
            newNode_left.parent = newNode.parent
            if (newNode.parent !== null) {
                if (newNode.parent.left === newNode) {
                    newNode.parent.left = newNode_left
                } else {
                    newNode.parent.right = newNode_left
                }
            } else {
                this.root = newNode_left
            }
            //剩余处理
            newNode_left.right = newNode
            newNode.parent = newNode_left
            return newNode_left
        } else {
            return null
        }
    }
    // 左旋转调整（可直接解决RR型）
    leftRotation(newNode) {
        if (newNode !== null) {
            // 保存失衡节点的右子树
            let newNode_right = newNode.right
            //处理失衡节点右子树的左子树
            newNode.right = newNode_right.left
            if (newNode_right.left !== null) {
                newNode_right.left.parent = newNode
            }
            newNode_right.parent = newNode.parent
            if (newNode.parent !== null) {
                if (newNode.parent.left === newNode) {
                    newNode.parent.left = newNode_right
                } else {
                    newNode.parent.right = newNode_right
                }
            } else {
                this.root = newNode_right
            }
            newNode_right.left = newNode
            newNode.parent = newNode_right
            return newNode_right
        } else {
            return null
        }
    }
    // 删除操作
    AVL_remove(element) {
        let node = this.AVL_research(element)
        if (node === null) {
            return false
        }
        // 标记是否发生了删除操作
        let flag = false
        let p = null
        let parent = node.parent
        let leftChild = node.left
        let rightChild = node.right

        // 要删除的节点是叶子节点
        // 执行后立即是完成一次删除操作，p记录删除后回退的父节点，node置空，标志位置true
        if (leftChild === null && rightChild === null) {
            if (parent !== null) {
                if (parent.left === node) {
                    parent.left = null
                } else {
                    parent.right = null
                }
                node.parent = null
            } else {
                this.root = null
            }
            p = parent
            node = null
            flag = true
        }
        // 要删除的节点仅有左子树
        // 同上可以立即完成一次删除操作
        else if (leftChild !== null && rightChild === null) {
            if (parent !== null) {
                if (parent.left === node) {
                    parent.left = leftChild
                } else {
                    parent.right = leftChild
                }
                leftChild.parent = parent
            } else {
                this.root = leftChild
                leftChild.parent = null
            }
            p = parent
            node = null
            flag = true
        }
        // 要删除的节点仅有右子树
        else if (leftChild === null && rightChild !== null) {
            if (parent !== null) {
                if (parent.left === node) {
                    parent.left = rightChild
                } else {
                    parent.right = rightChild
                }
                rightChild.parent = parent
            } else {
                this.root = rightChild
                rightChild.parent = null
            }
            p = parent
            node = null
            flag = true
        }
        // 既有左又有右
        else {
            //寻找需要删除的节点的中序顺序下的直接后继
            let successor = this.getSuccessor(node)
            //替代
            let temp = successor.data
            if (this.AVL_remove(temp)) {
                node.data = temp
            }
            flag = true
        }
        if (flag === true) {
            this.balance(node)
        }
        return flag
    }
    // 寻找传入节点中序顺序下的下一个节点
    getSuccessor(node) {
        if (node.right !== null) {
            let rightChild = node.right
            while (rightChild.left !== null) {
                rightChild = rightChild.left
            }
            return rightChild
        }
        // 在删除情况下传入的左右子树均不为空的节点不会进入这种情况
        else {
            let ancestor = node.parent
            while (ancestor !== null && ancestor !== ancestor.parent.left) {
                node = ancestor
                ancestor = node.parent
            }
            return ancestor.parent
        }
    }
}

module.exports = BalencedBinaryTree



// let arr = [53, 17, 78, 9, 45, 23, 65, 94, 81, 88]
// let bbt = BalencedBinaryTree.createByArr(arr)
// bbt.AVL_remove(45)
// bbt.inOrder()
// console.log(bbt.root.toString());